先簡單回顧一下，今天預計分析的題目：

如何利用 Bubble sort 進行排序?

1. 我們要將下圖六個數字進行從小到大的排序
   • 
2. 我們現在要把最大的放到最後一個位置(第六個位置)，所以我們會比較六個數字，兩兩做比較，逐漸將最大值向後移
   • 
3. 我們現在要把第二大的放到第五個位置，所以我們會比較剩下的五個數字，兩兩做比較，逐漸將最二大值向後移
   • 
4. 我們現在要把第三大的放到第四個位置，所以我們會比較剩下的四個數字，兩兩做比較，逐漸將第三大值向後移，以此類推，直到將全部的數字排列完成
   • 
5. 我們就會發現有N個數字
   • 我們就要比較 N-1 輪，才能把全部數字排列完
   • 我們要把數字放到正確的第 j 個位置，我們就會比較剩下的 j 個數字
6. 最終排序過程如下
   • 
     (動畫來源於 https://pjchender.blogspot.com/2017/09/bubble-sort.html )

• python 實作 bubble sort 如下

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
#       若有 N 個數字要排序，則要執行 N-1 輪
        for i in range(len(nums)-1,0,-1):
#           每次比較會從 0 ~ i-1 個做比較，每次會把最大的數字丟到最後面 
            for j in range(i):
#               若第 j 筆資料 大於 第 j+1 筆資料，則兩兩交換
                if nums[j] > nums[j+1]:
                    t = nums[j]
                    nums[j] = nums[j+1]
                    nums[j+1] = t
        return nums

• 不過你可以看見，Bubble Sort 基本上需要兩個迴圈執行，才能排序完成，加上需要不斷交換位置，才能將數字排序到正確的位置，在面對多筆資料需要排序的情況下，Bubble Sort 排序效率太低，當資料量變多，便容易造成 Time Limit Exceeded 的情況
• 由於 Bubble Sort 過程容易理解與實作，是排序的基本算法，也是面試常考的算法之一，故在此系列文章提出來做介紹
• 明天我們將介紹 Quick Sort，能夠減少排序時間，並且解決 912. Sort an Array 題目